#include <vector>
#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <climits>
#include <functional>
using namespace std;

class Solution
{
public:
    int minScoreTriangulation(vector<int> &v)
    {
        int n = v.size();
        vector<vector<int>> memo(n, vector<int>(n, -1)); // -1 表示没有计算过

        // lambda 递归函数
        function<int(int, int)> dfs = [&](int i, int j) -> int
        {
            if (i + 1 == j)
            {
                return 0; // 只有两个点，无法组成三角形
            }
            int &res = memo[i][j]; // 注意这里是引用，修改 res 相当于修改 memo[i][j]
            if (res != -1)
            { // 之前计算过
                return res;
            }
            res = INT_MAX;
            for (int k = i + 1; k < j; k++)
            { // 枚举顶点 k
                res = min(res, dfs(i, k) + dfs(k, j) + v[i] * v[j] * v[k]);
            }
            return res;
        };
        return dfs(0, n - 1);
    }
};

// int main() {
//     Solution s;
//     vector<int> v = {1, 2, 3};
//     cout << s.minScoreTriangulation(v) << endl; // 输出 6
//     return 0;
// }
/* t_semget.c

   Licensed under GNU General Public License v2 or later.
*/
/*  file: sem_demo.c  */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/shm.h>
#include <sys/wait.h>
#include <errno.h>

/* ---------- 信号量操作 ---------- */
int sem_id;       // 信号量集合标识符
#define SEM_NUM 1 // 本例只使用一个信号量

/* 初始化信号量（值设为 1，表示资源空闲） */
int set_semvalue(void)
{
    union semun
    {
        int val;               // 设置值
        struct semid_ds *buf;  // 不使用
        unsigned short *array; // 不使用
    } sem_union;

    sem_union.val = 1; // 初始计数为 1（互斥锁）
    if (semctl(sem_id, 0, SETVAL, sem_union) == -1)
    {
        perror("semctl SETVAL");
        return 0;
    }
    return 1;
}

/* 删除信号量 */
void del_semvalue(void)
{
    if (semctl(sem_id, 0, IPC_RMID) == -1)
    {
        perror("semctl IPC_RMID");
    }
}

/* P 操作（wait） */
int semaphore_p(void)
{
    struct sembuf sem_b;
    sem_b.sem_num = 0; // 第 0 个信号量
    sem_b.sem_op = -1; // -1 表示请求资源（P）
    sem_b.sem_flg = SEM_UNDO;
    if (semop(sem_id, &sem_b, 1) == -1)
    {
        perror("semop P");
        return 0;
    }
    return 1;
}

/* V 操作（post） */
int semaphore_v(void)
{
    struct sembuf sem_b;
    sem_b.sem_num = 0;
    sem_b.sem_op = 1; // +1 表示释放资源（V）
    sem_b.sem_flg = SEM_UNDO;
    if (semop(sem_id, &sem_b, 1) == -1)
    {
        perror("semop V");
        return 0;
    }
    return 1;
}

/* ---------- 共享内存（演示资源） ---------- */
int shm_id;
int *shared_counter; // 共享计数器

int main(void)
{
    key_t key;
    pid_t pid;

    /* 1️⃣ 创建/获取信号量集合 */
    key = ftok("/tmp", 'E'); // 生成唯一键值
    if (key == -1)
    {
        perror("ftok");
        exit(EXIT_FAILURE);
    }
    sem_id = semget(key, SEM_NUM, IPC_CREAT | 0666);
    if (sem_id == -1)
    {
        perror("semget");
        exit(EXIT_FAILURE);
    }

    /* 2️⃣ 初始化信号量 */
    if (!set_semvalue())
    {
        del_semvalue();
        exit(EXIT_FAILURE);
    }

    /* 3️⃣ 创建共享内存 */
    shm_id = shmget(key, sizeof(int), IPC_CREAT | 0666);
    if (shm_id == -1)
    {
        perror("shmget");
        del_semvalue();
        exit(EXIT_FAILURE);
    }
    shared_counter = (int *)shmat(shm_id, NULL, 0);
    if (shared_counter == (void *)-1)
    {
        perror("shmat");
        del_semvalue();
        exit(EXIT_FAILURE);
    }
    *shared_counter = 0; // 初始化计数器

    /* 4️⃣ 创建子进程，演示互斥访问 */
    pid = fork();
    if (pid < 0)
    {
        perror("fork");
        del_semvalue();
        exit(EXIT_FAILURE);
    }
    else if (pid == 0)
    { // 子进程
        for (int i = 0; i < 5; ++i)
        {
            semaphore_p(); // 进入临界区
            int val = (*shared_counter)++;
            printf("子进程 (pid=%d) 计数器 = %d\n", getpid(), val);
            semaphore_v(); // 离开临界区
            sleep(1);
        }
        exit(0);
    }
    else
    { // 父进程
        for (int i = 0; i < 5; ++i)
        {
            semaphore_p();
            int val = (*shared_counter)++;
            printf("父进程 (pid=%d) 计数器 = %d\n", getpid(), val);
            semaphore_v();
            sleep(1);
        }
        wait(NULL); // 等待子进程结束
    }

    /* 5️⃣ 清理资源 */
    shmdt(shared_counter);
    shmctl(shm_id, IPC_RMID, NULL);
    del_semvalue();

    return 0;
}
